/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: tao
 * Date: 2023-10-30
 * Time: 15:07
 */
public class KmpTest {
    public static void getNext(String sub, int[] next) {
        next[0] = -1;
        next[1] = 0;
        int i = 2;//提前走了一步
        int k = 0;//前一项的k
        //i下标从2开始
        for(;i <= sub.length(); i++) {
            //p[i-1] = p[k]
            if (k == -1 || sub.charAt(i - 1) == next[k]) {
                next[i] = k + 1;
                k++;
            } else {
                //回退
                k = next[k];
            }
        }
    }
    public static int kmp(String str, String sub, int pos) {
        if(str == null || sub == null) {
            return -1;
        }
        //pos：从pos开始遍历
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) {
            return -1;
        }
        if(pos < 0 || pos >= lenStr) {
            return -1;
        }
        int i = pos;//遍历str的下标
        int j = 0;//遍历sub的下标
        int[] next = new int[lenSub];
        getNext(sub, next);
        while(i < lenStr && j < lenSub) {
            if(j == -1 || str.charAt(i) == sub.charAt((j))) {
                i++;
                j++;
            } else {
                //i不回退，j回退到next[j]位置
                j = next[j];
            }
        }
        if(j >= lenSub) {
            return i - j;
        }
        return -1;
    }

    public static void main(String[] args) {
        String str = "ababcabcde";
        String sub = "abcd";
        int ret = kmp(str,sub,0);
        System.out.println(ret);
    }
}
